/******************************************************************************
 * $Id: sort.c,v 1.16 2004/09/22 01:14:23 jimb Exp $
 * @file
 * @author  Jim Brooks http://www.jimbrooks.org
 * @brief   Sort functions tailored for GLIB.
 * @remarks Some inline functions reside at sort.h
 ******************************************************************************/

#include "common.h"
#include "sort.h"

#include "tags.h"
#include "widgets.h"
#include "statusbar.h"

#define SORT_COMPARE( a, b )	ResortTagsGlistCompare( a, b )

/******************************************************************************
 * Sort a GList using an algorithm based on insertion-sort and bucket-search.
 * @param   pGlist
 *          tagsSorted (GLOBAL/IN/OUT) [ specific to hypersrc ]
 *          Amount of items sorted returned, caller is expected to first clear this.
 * @return  A pointer to the head link in the sorted the GList.
 * @remarks @verbatim
 * In this implementation, the sorted end of the list begins at the first link,
 * growing towards the last link of the list.
 * When finished, the first link will be the least, the last link will be greatest.
 *   +--------+
 *   |        | <--- last link in GList
 *   |        |
 *   |unsorted|
 *   |        |
 *   |        | <-- from where next unsorted item to sort is yanked
 *   +--------+ <-- border of lists
 *   |        | <-- pItemSortedLast (greatest sorted item)
 *   |        |
 *   | sorted |
 *   |        |
 *   |        | <-- smallest sorted item (first link in GList)
 *   +========+
 * @endverbatim
 ******************************************************************************/
GList*
InsertionSortGlist( GList* pGlist )
{
   GList*  pItemSortedLast		= NULL;
   GList*  pItemUnsorted		= NULL;
   GList*  pItemUnsortedNext	= NULL;
   GList*  pItemSorted			= NULL;
   GList** ppBucket				= NULL;
   int     direction;
   int     idxBucket;
   static GList* buckets[256];
#ifdef HYPERSRC_PEDANTIC
   int items = g_list_length( pGlist );
#endif

  /*
   * Return if only one link (which is inherently sorted).
   */
   if ( pGlist->next == NULL ) return pGlist;

  /*
   * To speed searching the sorted items, create a set of bucket pointers.
   * Note that these bucket pointers point SOMEWHERE WITHIN A BUCKET.
   */
   ppBucket = memset( &buckets, 0, sizeof(buckets) );

  /*
   * The sorted sub-list begins as the first link.
   * The unsorted sub-list begins as the second link (and any following links).
   * Set the pointer to the last item in the sorted sub-list.
   */
   pItemSortedLast = pGlist;

  /*
   * For each unsorted item.
   *
   * Note that the unsorted item might be re-linked inside of the loop,
   * which means "next" pointer might be changed to point within the sorted sub-list.
   * To correctly iterate thru the unsorted sub-list, the loop is based
   * on a variable (pItemUnsortedNext) that isn't affected by the loop body.
   */
   pItemUnsortedNext = pItemSortedLast->next;
   for (;;)
   {
      pItemUnsorted     = pItemUnsortedNext;
      pItemUnsortedNext = pItemUnsortedNext->next;

     /* - - - - - - - specific to hypersrc - - - - - - - - - */
     {
        /*
         * If the percentage has increased by 5%, then update the statusbar.
         * "tagsSortedPercentShown" holds the previous percentage being shown.
         * Because computing the percentage will slow this inner loop,
         * only do so periodically.
         */
         ++tagsSorted;
         if ( (tagsSorted & 0x3ff) == 0 )
         {
            int percent = (int) ( (float)(tagsSorted) / (float)tagsCnt * 100 );
            ProcessPendingEvents();
            if ( percent - tagsSortedPercentShown >= 5 )
            {
               tagsSortedPercentShown = percent;
               if ( tagsCnt > 100 ) StatusbarShowPercentage( "Tags sorted: __%.", percent );
            }
         }
      }
     /* - - - - - - - specific to hypersrc - - - - - - - - - */

     /*
      * Is this unsorted item already in its sorted position?
      * It is if the unsorted item is >= the greatest (last) sorted item.
      */
      if ( SORT_COMPARE( pItemUnsorted->data, pItemSortedLast->data ) >= 0 )
      {
        /*
         * Expand the sorted sub-list to absorb the formerly unsorted item,
         * continue to next unsorted item.
         */
         pItemSortedLast = pItemUnsorted;
         goto next_unsorted_item;
      }

     /*
      * Determine if there is a bucket that corresponds
      * to the first char of the unsorted item.
      */
      idxBucket = *(unsigned char*)(pItemUnsorted->data);
      pItemSorted = ppBucket[idxBucket];
      if ( pItemSorted )
      {
        /*
         * There is a bucket.
         * Determine whether to begin the search backwards or forwards.
         */
         direction = SORT_COMPARE( pItemUnsorted->data, pItemSorted->data );
      }
      else
      {
        /*
         * No bucket yet, assign pItemSorted (which is now NULL).
         * Search will begin from last sorted item, scanning downwards.
         */
         direction = -1;
         pItemSorted = pItemSortedLast->prev;
      }

     /*
      * This unsorted item needs to be inserted somewhere in the sorted sub-list.
      * Find the position in sorted sub-list where the unsorted item belongs.
      * Iterate backwards for each sorted item greater than this unsorted item.
      */
      if ( direction >=0 ) goto search_forward;

     /*
      * Search backwards.
      */
      for ( ;
            pItemSorted != NULL;
            pItemSorted = pItemSorted->prev )
      {
        /*
         * For searching backwards, is this sorted item <= unsorted item?
         */
         if ( SORT_COMPARE( pItemSorted->data, pItemUnsorted->data ) <= 0 )
         {
           /*
            * Encountered a sorted item that is <= the unsorted item,
            * which means the unsorted item belongs immediately after.
            */
            break;
         }
      }
      goto skip_search_forward;

     /*
      * Search forward.
      */
      search_forward:
      for ( ;
            pItemSorted != NULL;
            pItemSorted = pItemSorted->next )
      {
        /*
         * For searching forwards, is this sorted item > unsorted item?
         */
         if ( SORT_COMPARE( pItemSorted->data, pItemUnsorted->data ) > 0 )
         {
           /*
            * Encountered a sorted item that is > the unsorted item,
            * which means the unsorted item belongs immediately before.
            * Revert to sorted item which precedes the unsorted item.
            */
            pItemSorted = pItemSorted->prev;
            break;
         }
      }

      skip_search_forward:

     /*
      * Done iterating thru the sorted sub-list, but why?
      * Either the preceding sorted item, or end-of-list, was encountered,
      * so either insert or prepend the unsorted item, resp.
      *
      * Unlink the unsorted item.
      */
      GlistRemoveNonFirstLink( pGlist, pItemUnsorted );

      if ( pItemSorted != NULL )
      {
        /*
         * Encountered a sorted item <= unsorted item.
         * Insert the unsorted item after this sorted item.
         */
         GlistInsert( pItemSorted, pItemUnsorted );
      }
      else
      {
        /*
         * The unsorted item belongs at the start of the list
         * (so far it has the least value).
         * Prepend the unsorted item.
         */
         GlistPrepend( pGlist, pItemUnsorted );
         pGlist = pItemUnsorted;
      }

     /*
      * If there was no bucket pointer, now assign one.
      * (Actually, just doing an assignment is faster.)
      */
      ppBucket[idxBucket] = pItemUnsorted;

     /*
      * To next unsorted item... 
      */
      next_unsorted_item:

      if ( pItemUnsortedNext == NULL ) break;
   }

  /*
   * Loops are done, return.
   */
#ifdef HYPERSRC_PEDANTIC
   g_assert( pGlist  && (items == g_list_length( pGlist)) );
#endif
   return pGlist;
}
